/*
已知序列R，长度为n，求个数大于n/2的元素，没有则返回-1
*/

#include<iostream>
#include<vector>
using namespace std;

// 求候选多数元素 -- 如果两个元素不同，则删除
int candidate(vector<int> &R)
{
	int c=R[0], cnt=1;
	int i=1;
	
	while(i < R.size())
	{
		// 选择两个元素(R[i], c)
		if(R[i]==c)
			cnt++; // 相同时累加
		
		// 不相同时递cnt，相当于删除这两个元素
		else
			cnt--;
		
		// cnt为0时对剩余元素从头开始查找
		if(cnt==0)
		{
			i++;
			c=R[i];
			cnt++;
		}
		i++;
	}
	
	return c;
}

// 求多数元素
int majority(vector<int>& R)	
{
	// 无多数元素
	if(R.size()==0 || R.size()==1)
		return -1;
	
	// 找到候选元素
	int c = candidate(R);
	
	// 统计候选元素个数
	int cnt=0;
	for(int i=0; i<R.size(); i++)
		if(R[i]==c) cnt++;
	
	// 返回结果
	if(cnt > R.size()/2)
		return c;
	else
		return -1;
}

int main()
{
	// 创建序列R
	vector<int> a={1, 2, 2};
	
	// 求多数元素
	int c = majority(a);
	
	// 打印结果
	if(c != -1)
		printf(" 多数元素=%d\n", majority(a));
	else
		printf(" 不存在多数元素\n");
	
	return 0;
}
